package demo1;

public class DynamicPlanningPractise {
    /**
     * 买卖股票的最佳时期（含冷冻期）
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int maxProfit(int[] prices) {
        //使用状态机进行分析：
        //目前存在的状态 买入（持有股票），冻结期（卖出股票后），交易期
        //状态表示：创建一个一个nx3的二维数组，dp[n][0] 代表可交易 dp[n][1]代表买入， dp[n][2]代表冷冻期
        /**状态转移方程：由状态机得：
         dp[n][0] = Math.max(dp[n-1][0],dp[n-1][2]); -->可交易
         dp[n][1] = Math.max(dp[n-1][1],dp[n-1][0]-prices[n]); -->买入
         dp[n][2] = dp[n-1][1] + prices[n] -->冻结期

         初始化：
         由状态转移方程可得，对n位置填表其依赖于n-1处下标，故需要对第一天进行初始化*/
        int n = prices.length;
        if(n == 1) return 0; //当股票仅有一天时，买入多少就亏多少
        //1 创建dp表
        int[][] dp = new int[n][3];
        //2 初始化
        dp[0][1] = 0-prices[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        //4 返回值
        return Math.max(Math.max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
    }
    /**
     * 买卖股票的最佳时机含手续费
     * 时间复杂度O(n)
     * 空间复杂度O(n)*/
    public int maxProfit(int[] prices, int fee) {
        /**不可以当天买入再当天卖出，这样会平白无故亏损手续费 */
        /**
         状态表示：
         创造一个n*2的二维数组，dp[i][0] = 可交易 dp[i][1] = 买入

         状态转移方程：
         dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
         dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);

         初始化：
         dp[0][0] = 0;
         dp[0][1] = -prices[0];

         返回值：
         返回Math.max(dp[i][0],dp[i][1]);
         */
        int n = prices.length;
        //1 创建dp表
        int[][] dp = new int[n][2];
        //2 初始化
        dp[0][1] = -prices[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        //4 返回值
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
}
